package club.xiaojiawei.binarytree;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/19/22 11:56 PM
 * @question 669. 修剪二叉搜索树
 * @description 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
 * 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
 */
public class TrimBST669 {

    public static void main(String[] args) {
        TrimBST669 test = new TrimBST669();
        TreeNode root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        TreeNode result = test.trimBST(root, 3, 4);
        System.out.println(result);
    }

    /**
     * 递归
     * @param root
     * @param low
     * @param high
     * @return
     */
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null){
            return null;
        }
        if (root.val > high){
            if (root.left == null){
                return null;
            }
            root.val = root.left.val;
            root.right = root.left.right;
            root.left = root.left.left;
            root = trimBST(root, low, high);
        }else if (root.val < low){
            if (root.right == null){
                return null;
            }
            root.val = root.right.val;
            root.left = root.right.left;
            root.right = root.right.right;
            root = trimBST(root, low, high);
        }else {
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
        }
        return root;
    }

    /**
     * 官方-递归
     * @param root
     * @param L
     * @param R
     * @return
     */
    public TreeNode trimBST2(TreeNode root, int L, int R) {
        if (root == null) {
            return null;
        }
        if (root.val > R) {
            return trimBST2(root.left, L, R);
        }
        if (root.val < L) {
            return trimBST2(root.right, L, R);
        }
        root.left = trimBST2(root.left, L, R);
        root.right = trimBST2(root.right, L, R);
        return root;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
